<!DOCTYPE html>
<html lang="zh-cn">
<head>
    <title>不定方程</title>
    <meta charset="utf-8" />
    <link rel="stylesheet" type="text/css" href="../../css/note.css" />
</head>
<body>

<p class="example">
  解关于 `x, y` 的不定方程 `a x y+b x+c y+d = 0`, `a, b, c, d` 为整数.
</p>

<p class="solution">
  两边同乘 `a` 以后变形为
  <span class="formula">
    `(a x+c)(a y+b) = b c-a d`,
  </span>
  再讨论 `b c-a d` 的因子即可.
</p>

<p class="example">
  解关于 `a, b, c, d` 的不定方程 `1/a + 1/b + 1/c + 1/d = 1`,
  `a, b, c, d` 是两两不相等的正整数.
</p>

<p class="example">
  解关于 `x, y` 的不定方程 `x^2 + 615 = 2^y`.
</p>

<ol class="solution">
  <li>模 2:
    显然 `y` 只能是正整数, 于是 `2^y` 是偶数. 这推出方程左边是偶数,
    于是 `x` 是奇数.
  </li>
  <li>模 3: `2^y` 不是 3 的倍数, 但 615 是 3 的倍数, 于是 `x` 不是
    3 的倍数.
  </li>
  <li>模 6: 综上可知 `x = 6n+-1`, 于是 `x^2 -= 1 (mod 6)`.
    而 `615 -= 3 (mod 6)`, 得到 `2^y -= 4(mod 6)`. 这推出 `y` 是偶数.
  </li>
  <li>设 `y = 2n`, 原方程变形为
    <span class="formula">
      `(2^n - x)(2^n + x) = 615 = 3*5*41`,
    </span>
    我们只需寻找 `(a, b)` 满足 `a + b = 2^(n+1)`, 其中 `a, b in {3, 5,
    41}`. 容易发现只有两组解 `(a, b) = (5, 123)` 或 `(123, 5)`.
    于是
    <span class="formula">
      `2^n +- x = 5`, `quad 2^n &pm; x = 123`.
    </span>
    解得 `n = 6`, (于是 `y = 12`), `x = +-59`.
  </li>
</ol>

<p class="example">
  [来自 我是小学二年级的屑] 求 `{ x y = 4 n; x+y = n+2 :}` 的正整数解.
</p>

<ol class="solution">
  [来自 CBY 博士] 由已知
  <span class="formula">
    `x, y = (n+2+-sqrt((n-6)^2-32))/2`.
  </span>
  令判别式 `(n-6)^2-32 ge 0` 得 `n ge 12`. 令 `m = n-6 ge 6`, 则
  <span class="formula">
    `x = 4 + (m-sqrt(m^2-32))/2`
    `= 4 + 16/(m+sqrt(m^2-32))`.
  </span>
  因此
  <span class="formula">
    `4 lt x`
    `le 4 + 16/(6+sqrt(6^2-32)) = 6`,
  </span>
  即 `x = 5, 6`.
  <li>`x = 6` 对应 `m = 6`, `n = 12`, 这时 `y = 8`.</li>
  <li>`x = 5` 对应 `m - sqrt(m^2 - 32) = 2`, 即 `m = 9`, `n = 15`, 这时 `y
    = 12`.</li>
</ol>

<p class="example">
  求 `(x+y)^2 = x^3 + y^3` 的正整数解.
</p>

<p class="solution">
  两边同时约去正因子 `x+y` 得
  <span class="formula">
    `x+y = x^2 - x y + y^2`,
  </span>
  这是椭圆的方程, 由图像我们推测正整数解只有 `(1,2)`, `(2,1)`, `(2,2)`.
  <span class="img sm">
    <img src="../img/diophantine-01.png" alt="">
  </span>
  [来自 我是费马方程的正整数解]
  上式视为 `x` 的方程, 令它的判别式 `ge 0`, 我们得到 `y = 1, 2`,
  从而轻松得到结果.
</p>

<p class="example">
  求 `x^3 + y^3 = z^2` 的正整数解.
</p>

<p class="solution">
  令 `(x, y, z) = (a c, b c, c^2)`, 问题化为
  <span class="formula">
    `a^3 c^3 + b^3 c^3 = c^4`,
  </span>
  显然 `c != 0`, 得 `a^3 + b^3 = c`. 任取 `a, b in ZZ^+`,
  <span class="formula">
    `(x, y, z) = (a (a^3+b^3), b (a^3+b^3), (a^3+b^3)^2)`
  </span>
  都给出原方程的一组正整数解;
  如 `a=1, b=1` 时得到 `(2, 2, 4)`, `a=1, b=2` 时得到 `(9, 18, 81)` 等.
  其它形式的解??
</p>

<p class="example">
  [来自 马上开学的菜狗]
  求 `x^3 + y^3 = x^2 y^2` 的正整数解.
</p>

<p class="solution">
  [来自 小猿搜题] 取参数 `t = x // y`, 方程化为 `(t^3+1) y^3 = t^2 y^4`,
  从而
  <span class="formula">
    `{ x = t^2 + 1//t; y = t + 1//t^2 :}`
  </span>
  `t = 1` 时, 得到一组解 `x = y = 2`.
  `t gt 1` 时, ??
</p>

<p class="example">
  [来自 叉叉子]
  证明不定方程 `2x^4 = y^4 - 17 z^4` 只有平凡解 `x = y = z = 0`.
</p>

<p class="proof">
  由于方程齐次, 不妨令 `gcd(x, y, z) = 1`,
  考虑 mod 17 的可能余数:
  <span class="formula">
    `{:
      2x^4, y^4, 17z^4;
      0, 0, 0;
      +-2, +-1, ;
      +-8, +-4, ;
    :}`
  </span>
  等式不能成立, 一个矛盾.
</p>

<h2>勾股数</h2>

<p class="definition">
  由熟知的勾股定理 (Pythagorean theorem), 直角三角形的三边长 `a, b, c`
  满足
  <span class="formula">
    `a^2+b^2=c^2`.
  </span>
  我们称满足上述不定方程的正整数 `a, b, c` 为一组<b>勾股数
  (Pythagorean triple)</b>, 如 `3, 4, 5`; `5, 12, 13`;
  `7, 24, 25` 等. 以勾股数为边长的直角三角形叫勾股三角形.
  注意到像 `3, 4, 5` 与 `6, 8, 10` 是本质相同的勾股数, 故定义勾股数
  `a, b, c` 是<b>本原</b>的, 如果 `gcd(a, b, c) = 1`.
</p>

<p class="lemma">
    本原勾股数 `a, b, c` 两两互素, 且 `c` 为奇数, `a, b` 一奇一偶.
</p>

<p class="proof">
    设 `d = (a, b)`, 则 `d^2 | a^2 + b^2 = c^2`, 这推出 `d | c`.
    于是 `d | (a, b, c) = 1`, 即 `d = 1`. 同理 `(b, c) = (c, a) = 1`.<br/>
    因为 `(a, b, c)` 两两互素, 它们中的偶数不超过一个, 假设 `c` 为偶数,
    则 `a, b` 为奇数. 设
    <span class="formula">
        `a = 2m+1`, `quad b = 2n+1`, `quad c = 2k`,
    </span>
    则 `a^2 + b^2 -= 2 (mod 4)`, `c^2 -= 0 (mod 4)`, 矛盾.
    因此 `c` 为奇数. 注意到 `a, b` 不全为偶数, 其中一个为奇数,
    则另一个为偶数.
</p>

<p class="theorem">
    由于 `a, b` 地位对称, 不妨设 `b` 是偶数, 则本原勾股数的全体可以表示为
    <span class="formula">
        `a = u^2-v^2`, `quad b = 2u v`, `quad c = u^2+v^2`.
    </span>
    其中
    <span class="formula">
        `u gt v gt 0`, `quad (u, v) = 1`, 且 `u, v` 一奇一偶.
    </span>
</p>

<p class="proof">
    容易说明满足上述条件的 `(a, b, c)` 确实是本原勾股数. 下证必要性.
    注意 `c-a, c+a, b` 都是正的偶数, 可设
    <span class="formula">
        `2A = c-a`, `quad 2B = b`, `quad 2C = c+a`,
    </span>
    `A, B, C` 为正整数. 因为 `b^2 = c^2 - a^2 = (c-a)(c+a)`, 我们有
    <span class="formula">
        `B^2 = A C`.
    </span>
    下证 `A, C` 互素. 设 `d = (A, C)`, 则
    <span class="formula">
        `d | C-A = a`, `quad d | C+A = c`,
    </span>
    从而 `d | (a, c) = 1`, 即 `d = 1`.<br/>
    因为 `A C` 是平方数, 而 `A, C` 没有公共的素因子, 所以 `A, C`
    都是平方数, 可设
    <span class="formula">
        `C = u^2`, `quad A = v^2`.
    </span>
    于是
    <span class="formula">
        `a = u^2-v^2`, `quad c = u^2+v^2`,<br/>
        `b = 2 sqrt(B^2)`
        `= 2 sqrt(A C)`
        `= 2 u v`.
    </span>
    最后说明 `u, v` 满足的条件. 由 `C gt A` 有 `u gt v gt 0`.
    由 `(A, C) = 1` 知 `(u, v) = 1`. 由 `a = u^2 - v^2` 是奇数知 `u, v`
    一奇一偶.
</p>

<ol class="proof">
    下面使用数形结合的直观重新证明这一定理.
    <li>首先说明, 全体本原勾股数与单位圆在第一象限上的有理点一一对应.
        方程两边同除以 `c^2` 得
        <span class="formula">
            `(a/c)^2 + (b/c)^2 = 1`,
        </span>
        这说明 `(a/c, b/c)` 是单位圆周上的点; 反之设 `(p, q)`
        是单位圆上的有理点, 其中 `p, q` 是最简分数,
        用它们分母的最小公倍数通分得到
        `(p, q) = (a/c, b/c)`, 从而对应于勾股数 `(a, b, c)`.
        容易说明 `(a, b, c)` 是本原的.
    </li>
    <li>在第一象限的单位圆周上任取一点 `P(x_P, y_P)`. 又设 `A(-1, 0)`,
        `k` 是 `AP` 的斜率, 则 `P` 点坐标和 `k` 的值一一对应.
        显然 `P` 是有理点时, `k` 是 `(0,1)` 中的一个有理数;
        下证 `k` 是 `(0,1)` 中的有理数时, 点 `P` 必为有理点.
        <span class="img lg">
            <img src="../img/pythagorean-triple.svg" />
        </span>
        设 `k = v/u`, 整数 `u gt v gt 0`, 我们求 `P` 的坐标,
        可以用 `tan 2 alpha` 的公式; 这里用复数来处理.
        由已知, `"arg"(u+"i"v) = /_ PAQ`, 将这个复数平方,
        就得到一个具有两倍辐角的复数
        `(u+"i"v)^2 = u^2-v^2 + 2u v"i"`.
        因为同弧所对的圆心角是圆周角的两倍, 我们有
        <span class="formula">
            `"arg"(u+"i"v)^2 = /_ POQ`.
        </span>
        又
        <span class="formula">
            `|(u+"i"v)^2|`
            `= |u+"i"v|^2`
            `= u^2+v^2`.
        </span>
        利用三角形相似得到 `x_P = (u^2-v^2)/(u^2+v^2)`,
        `y_P = (2u v)/(u^2+v^2)`, 所以 `P` 是有理点.
    </li>
    <li>只要让斜率 `k` 取遍集合 `(0,1) nn QQ`,
        就得到单位圆在第一象限的全部有理点,
        从而得到全体本原勾股数.
    </li>
</ol>

<p class="remark">
  可以用代数计算验证, 确实有
  <span class="formula">
    `(u^2-v^2)^2 + (2u v)^2 = (u^2+v^2)^2`.
  </span>
  由以上讨论知, 任意一个勾股三角形总是相似于边长为
  `u^2-v^2, 2u v, u^2+v^2` 的三角形, 其中 `u gt v gt 0`.
  代入 `(u,v) = (2,1)` 得到勾股数 `(3, 4, 5)`, 代入 `(u,v) = (3,2)`
  得到勾股数 `(5,12,13)`... 试试看吧!
</p>

<p class="example">
  [来自 レイ]
  证明: 单位圆上存在无数个点, 它们两两间的距离均为有理数.
</p>

<p class="proof">
  [来自 折棒的网友]
  记 `A(-1, 0)`, `B(1, 0)`.
  对于任一组勾股数 `a^2+b^2=c^2`, 可取点 `K` 使得 `KA = 2a//c`, `KB
  = 2b//c`, 于是 `KA^2 + KB^2 = AB^2`, `K` 位于单位圆上.
  依此法取 `K_1, K_2`, 则 `A B K_1 K_2` 是圆内接四边形, 由 Ptolemy 定理
  <span class="formula">
    `K_1 K_2 * AB + B K_1 * A K_2 = A K_1 * B K_2`.
  </span>
  因此 `K_1 K_2` 为有理数.
  但勾股数有无穷多组, 所以这样的点有无穷多个.
</p>

<p class="lemma">
    不存在面积为平方数的勾股三角形.
</p>

<ol class="proof">
    本证明使用无穷递降法.
    <li>设该勾股三角形的三边长为 `a, b, c`, 面积为 `d^2`.
        若 `(a, b, c) = m gt 1`, 则 `m^2 | a b = 2 d^2`,
        这<a href="0.html#exp-a^2|kb^2">推出 `m | d`</a>.
        因此不妨设 `a, b, c` 是本原的, 从而得到已知条件
        <span class="formula">
            `a^2 + b^2 = c^2`,
            `quad (a, b, c) = 1`,
            `quad a b // 2 = d^2`.
            <span class="label" id="for-inf-cond-abc"></span>
        </span>
        我们假设 `c` 是满足上述条件的最小正整数, 下面来导出矛盾.
    </li>
    <li>由勾股数的结论, `a, b, c` 两两互素. 设 `b` 是偶数,
        则存在整数 `u, v`, 满足
        <span class="formula">
            `u gt v gt 0`,
            `quad (u, v) = 1`,
            `quad u, v` 一奇一偶,
        </span>
        使得
        <span class="formula">
            `a = u^2 - v^2`, `quad b = 2uv`, `quad c = u^2 + v^2`.
        </span>
        于是
        <span class="formula">
            `d^2 = a b // 2 = (u+v)(u-v) u v`.
        </span>
    </li>
    <li>容易验证四个因子 `u+v, u-v, u, v` 两两互素. 比如
        <span class="formula">
            `(u+v, u-v)`
            `= (u+v, (u+v)+(u-v))`
            `= (u+v, 2 u)`,
        </span>
        但 `u + v` 是奇数, 因此上式等于 `(u+v, u) = (v, u) = 1`, 这推出
        `(u+v, u-v) = 1`.
    </li>
    <li>四个互素因子的乘积是平方数 `d^2`, 由此得到这四个因子都是平方数.
        设
        <span class="formula">
            `A = sqrt(u+v)`, `quad B = sqrt(u-v)`,
            `quad C = sqrt u`, `quad D = sqrt v`,
        </span>
        `A, B, C, D` 也是两两互素的,
        其中 `A gt B gt 0` 是奇数, `C, D` 一奇一偶.  注意
        <span class="formula">
            `2C^2 = 2u = A^2 + B^2 -= 2 (mod 4)`,
        </span>
        所以 `C` 是奇数, `D` 是偶数.
    </li>
    <li>令
        <span class="formula">
            `a_1 = (A+B)/2`, `quad b_1 = (A-B)/2`,
            `quad c_1 = C`, `quad d_1 = D/2`,
        </span>
        有
        <span class="formula">
            `a_1^2 + b_1^2 = (A^2+B^2)/2 = C^2 = c_1^2`,<br/>
            `a_1 b_1 // 2 = (A^2-B^2)/8 = v/4 = (D/2)^2 = d_1^2`.
        </span>
        且
        <span class="formula">
            `(a_1, b_1, c_1)`
            `= (a_1, a_1+b_1, c_1)`
            `= (a_1, A, C) = 1`.
        </span>
    </li>
    <li>我们发现, `a_1, b_1, c_1` 也满足 `a, b, c` 的关系
        <a class="ref" href="#for-inf-cond-abc"></a>,
        但 `c_1 = C = sqrt u lt u^2+v^2 = c`, 这与 `c` 的最小性矛盾.
        原命题得证.
    </li>
</ol>

<p class="theorem">
    <b>Fermat 大定理 (Fermat's Last Theorem, FLT)</b>
    设整数 `n gt 2`, 则不定方程
    <span class="formula">
        `x^n + y^n = z^n`
    </span>
    不存在满足 `x, y, z != 0` 的整数解.
</p>

<ol class="proof">
    我们有以下观察:
    <li>该不定方程是齐次的. 即, 若 `x, y, z` 是该方程的解,
    则对任意整数 `k`, `k x, k y, k z` 也是它的解.
    反之若存在非零整数 `k`, 使得 `k x, k y, k z` 是方程的解,
    则 `x, y, z` 也是它的解.
    </li>
    <li>若 FLT 对于整数 `n` 成立, 则它对任意 `n` 的倍数也成立.</li>
    我们来证明 FLT(4), 即 `n = 4` 的情形.
    设 `x^4 + y^4 = z^4`, 由观察 1, 可以假设 `(x, y, z) = 1`.
    因此, `x^2, y^2, z^2` 是本原勾股数. 设 `y` 是偶数, 故存在 `u, v` 使得
    <span class="formula">
        `x^2 = u^2 - v^2`,
        `quad y^2 = 2 u v`,
        `quad z^2 = u^2 + v^2`.
    </span>
    上式表明 `u, v, z` 是勾股数, 但它们围成的直角三角形的面积
    <span class="formula">
        `u v // 2 = (y/2)^2`
    </span>
    是平方数! 矛盾.
    <br/>
    既然 FLT(4) 已证, 由观察 2, 接下来只需考虑 `n` 为奇素数的情形.
    然而, 费马大定理是非常困难的问题,
    即使我有绝妙证法, 这里的空白也太小写不下.
</ol>

<p class="remark">
  `133^5 + 110^5 + 84^5 + 27^5 = 144^5`
</p>

<h2>平方和</h2>

<h3>二平方和</h3>

<p class="lemma">
  <b>二平方和恒等式</b>
  <span class="formula">
    `(x_1^2+x_2^2)(y_1^2+y_2^2)
    = (x_1 y_1+x_2 y_2)^2 + (x_1 y_2-x_2 y_1)^2`.
  </span>
  从而, 如果整数 `m, n` 能表示为两个整数的平方之和,
  则 `mn` 也能.
</p>

<p class="theorem">
  素数 `p` 能表为两个整数的平方和当且仅当 `p = 2` 或 `p -= 1 (mod 4)`.
  换言之, `4k+3` 型的素数不能表示为两个整数的平方和.
</p>

<ol class="proof">
  <li>`p = 2` 时显然有 `2 = 1^2 + 1^2`. 注意整数 `a` 的平方模 4 余 0 或 1,
    于是 `a^2 + b^2` 模 4 余 0, 1 或 2, 不可能为 3. 所以 `4k+3` 型素数不能表为平方和.
  </li>
  <li>下设 `p = 4k+1`.
    此时 `-1` 是模 `p` 的二次剩余, 故存在 `x, m` 使得 `x^2 + 1 = m p`, 其中
    `1 le x le p-1`, 于是
    <span class="formula">
      `m p le (p-1)^2 + 1 le (p-1)p`,
    </span>
    从而 `m lt p`.
  </li>
  <li>设 `m` 是使得关于 `x, y` 的不定方程
    <span class="formula">
      `x^2 + y^2 = m p`
    </span>
    有解的最小正整数, 由 1. 知 `m lt p`.
    下证必有 `m = 1`.  首先, 若 `m` 是 `x, y` 的公因数, 则有
    `m^2 | m p rArr m | p`, 再由 `m lt p` 推出 `m = 1`.
    下设 `m` 不是它们的公因数, 从而 `m gt 1`, 我们来导出矛盾.
    分别记 `a, b` 是 `x, y` 除以 `m` 的绝对最小余数, 则 `a, b` 不全为零,
    且绝对值小于等于 `m//2`. 因此
    <span class="formula">
      `0 lt a^2 + b^2 le 2 (m//2)^2 = m^2//2`.
    </span>
    且
    <span class="formula">
      `a^2 + b^2 -= x^2 + y^2 -= 0` `(mod m)`,
    </span>
    从而
    <span class="formula">
      `a^2 + b^2 = m q`, `quad 0 lt q le m//2 lt m`.
    </span>
  </li>
  <li>下证 `p q` 可以表示成两个整数的平方和, 从而推翻假设.
    由二平方和恒等式
    <span class="formula">
      `m^2 p q = (a^2+b^2)(x^2+y^2) = (a x+b y)^2 + (a y-b x)^2`,
      <span class="label" id="for-pq-2sum"></span>
    </span>
    其中
    <span class="formula">
      `a x + b y -= x^2 + y^2 -= 0 (mod m)`,
      `quad a y - b x -= 0 (mod m)`.
    </span>
    这指出 `m` 是 `a x + b y` 和 `a y - b x` 的公因数, 从而
    <a class="ref" href="#for-pq-2sum"></a> 两边可以同除 `m^2`,
    但 `q lt m`, 与 `m` 的最小性矛盾. 证毕.
  </li>
</ol>

<p class="theorem">
  <b>二平方和定理</b>
  正整数 `n` 能表为两个整数的平方和当且仅当它所有的 `4k+3` 型素因子在 `n`
  中的次数为偶数.
</p>

<ol class="proof">
  <li>充分性. 设 `n = t^2 n_1`, 其中 `n_1` 无平方因子.
    若 `4k+3` 型素因子在 `n` 中的次数均为偶数,
    则 `n_1` 不含 `4k+3` 型素因子, 因而 `n_1` 可以表为平方和 `a^2+b^2`,
    进而 `n` 可以表为平方和 `(t a)^2 + (t b)^2`.
  </li>
  <li>必要性. 设 `n = x^2 + y^2`, 但存在一个素因子 `p=4k+3`, 它在 `n`
    中的次数为奇数, 设这个次数为 `2j+1`.
    我们可以从 `n = x^2 + y^2` 两边约去公因子 `d^2`, 而且 `p` 在 `n//d^2`
    中的次数仍为奇数. 因此不妨设 `x, y` 互素. 如果 `p|x`, 则由 `p|n` 知
    `p|y`, 与 `x, y` 互素矛盾. 所以 `p!|x`, `p!|y`, 此时存在整数 `z` 使得
    `x z -= y` `(mod p)`. 从而有
    <span class="formula">
      `(1+z^2) x^2 -= x^2 + y^2 -= n -= 0` `(mod p)`,
    </span>
    于是 `1 + z^2 -= 0` `(mod p)`, 即 `-1` 是模 `p` 的二次剩余, 和 `p =
    4k+3` 矛盾.
  </li>
</ol>

<h3>四平方和</h3>

<p>本节将证明, 任意正整数可以表为四个整数的平方和. 其证明思路与二平方和定理类似.</p>

<a href="https://baike.baidu.com/item/%E5%9B%9B%E5%B9%B3%E6%96%B9%E5%92%8C%E5%AE%9A%E7%90%86?bk_fr=chain_bottom&timestamp=1568187163118">[来自百度百科]</a>

<p class="lemma">
  <b>Lagrange 恒等式</b>
  设 `n in ZZ^+`, `x_i, y_i in RR`, `i = 1, 2, cdots, n`, 则
  <span class="formula">
    `(sum_(i=1)^n x_i^2)(sum_(i=1)^n y_i^2)`
    `= (sum_(i=1)^n x_i y_i)^2
    + sum_(1 le i lt j le n) (x_i y_j - x_j y_i)^2`.
  </span>
  从向量的角度理解:
  <span class="formula">
    `|bm x|^2 |bm y|^2 = |bm x * bm y|^2 + |bm x xx bm y|^2`.
  </span>
</p>

<p class="proof">
  <span class="formula">
    右边
    `= sum_(i=1)^n x_i^2 y_i^2 + 2 sum_(1 le i lt j le n) x_i y_i x_j
    y_j + sum_(1 le i lt j le n) x_i^2 y_j^2`
    `- 2 sum_(1 le i lt j le n) x_i y_j x_j y_i
    + sum_(1 le i lt j le n) x_j^2 y_i^2`
    `= sum_(i=1)^n x_i^2 y_i^2 + sum_(1 le i lt j le n) x_i^2
    y_j^2 + sum_(1 le i lt j le n) x_j^2 y_i^2 =`左边.
  </span>
</p>

<p class="lemma">
  <b>四平方和恒等式</b> (Euler, 1743)
  <span class="formula">
    `(sum_(i=1)^4 x_i^2)(sum_(i=1)^4 y_i^2) = sum_(i=1)^4 z_i^2`.
  </span>
  其中
  <span class="formula">
    `z_1 = x_1 y_1 + x_2 y_2 + x_3 y_3 + x_4 y_4`,<br/>
    `z_2 = x_1 y_2 - x_2 y_1 + x_3 y_4 - x_4 y_3`,<br/>
    `z_3 = x_1 y_3 - x_3 y_1 + x_4 y_2 - x_2 y_4`,<br/>
    `z_4 = x_1 y_4 - x_4 y_1 + x_2 y_3 - x_3 x_2`.
  </span>
  从而, 如果整数 `m, n` 能表示为四个整数的平方之和,
  则 `mn` 也能.
</p>

<p class="proof">
  由 Lagrange 恒等式, 只需验证
  <span class="formula">
    `(x_1 y_2 - x_2 y_1)(x_3 y_4 - x_4 y_3)`
    `- (x_1 y_3 - x_3 y_1)(x_2 y_4 - x_4 y_2)`
    `+ (x_1 y_4 - x_4 y_2)(x_2 y_3 - x_3 y_2) = 0`.
  </span>
  即可. 上式的左边可由 Laplace 定理展开行列式
  <span class="formula">
    `|x_1,x_2,x_3,x_4;
      y_1,y_2,y_3,y_4;
      x_1,x_2,x_3,x_4;
      y_1,y_2,y_3,y_4|`
  </span>
  得到.
</p>

<p class="lemma" id="lem-4-square-odd-prime">
  (Euler, 1751) 对任意奇素数 `p`, 同余方程
  <span class="formula">
    `x^2+y^2+1 = 0` `(mod p)`
  </span>
  存在整数解 `0 le x, y lt p//2`.
  因此对任意奇素数 `p`, 存在正整数 `m` 和整数 `0 le x, y le (p-1)//2`,
  使得
  <span class="formula">
    `m p = x^2 + y^2 + 1 le (p-1)^2//2 + 1`
    `lt (p-1)(p+1) + 1 = p^2`.
  </span>
  因此 `m lt p`.
</p>

<p class="proof">
  模 `p` 的二次剩余 (即全体平方数 `ZZ^2` 模 `p` 的同余类)
  有 `(p+1)//2` 个, 分别为
  <span class="formula">
    `0, 1^2, 2^2, cdots, ((p-1)/2)^2`.
  </span>
  若 `(p-1)//2` 是模 `p` 的二次剩余, 则存在 `0 le x lt p//2`
  使得 `x^2 -= (p-1)//2` `(mod p)`, 于是 `1 + x^2 + x^2 -= 0` `(mod p)`,
  定理得证.<br/>
  若 `(p-1)//2` 不属于模 `p` 的二次剩余,
  将模 `p` 的剩余 (即全体整数模 `p` 的同余类)
  分为如下 `(p-1)//2` 组:
  <span class="formula">
    `{0, p-1}, {1, p-2}, cdots, {(p-1)/2, (p-1)/2}`.
  </span>
  而模 `p` 的 `(p+1)//2` 个二次剩余必然落在前 `(p-3)//2` 组当中.
  由鸽巢原理, 必有两个二次剩余落在同一组中. 由于每一组的两个元素
  `m, n` 满足 `m + n + 1 -= 0` `(mod p)`,
  故存在整数 `x, y`, `0 le x, y lt p/2`,
  使 `x^2 + y^2 + 1 -= 0` `(mod p)`.
</p>

<p class="theorem">
  <b>四平方和定理</b>
  (Lagrange, 1770; Euler, 1773)
  任何非负整数都可以表示为四个整数的平方之和, 即不定方程
  <span class="formula">
    `x_1^2 + x_2^2 + x_3^2 + x_4^2 = n`, `quad n ge 0`
  </span>
  恒有整数解.
</p>

<ol class="proof">
  <li>显然定理对 `n = 0, 1, 2` 成立:
    <span class="formula">
      `0 = 0^2 + 0^2 + 0^2 + 0^2`,<br/>
      `1 = 0^2 + 0^2 + 0^2 + 1^2`,<br/>
      `2 = 0^2 + 0^2 + 1^2 + 1^2`.
    </span>
    从而由四平方和恒等式知, 只需证定理对任意奇素数 `p` 成立.
    又由<a class="ref" href="#lem-4-square-odd-prime"></a>,
    存在最小的正整数 `m lt p` 使得 `m p` 能表示为四个整数的平方和:
    <span class="formula">
      `m p = x_1^2 + x_2^2 + x_3^2 + x_4^2`.
    </span>
  </li>
  <li>下证 `m` 不是偶数, 否则 `m p` 为偶数, `x_i, i = 1, 2, 3, 4`
    中的奇数只能是偶数个 (即 0, 2, 4 个).
    不失一般性, 设 `x_1, x_2` 奇偶性相同, 且 `x_3, x_4` 奇偶性相同, 则
    `x_1+-x_2`, `x_3+-x_4` 均为偶数, 得到
    <span class="formula">
      `(m//2)p = ((x_1+x_2)/2)^2 + ((x_1-x_2)/2)^2`
      `+ ((x_3+x_4)/2)^2 + ((x_3-x_4)/2)^2`.
    </span>
    然而 `m//2 lt m`, 这与 `m` 的最小性矛盾.
  </li>
  <li>下证 `m = 1`.  首先, 若 `m` 为 `x_1, x_2, x_3, x_4` 的公因数, 则有
    `m^2 | m p` `rArr m | p`, 再由 `m lt p` 推出 `m = 1`.
    下设 `m` 不是它们的公因数, 从而 `m` 是大于 `1` 的奇数, 我们来导出矛盾.
    取 `y_i` 为 `x_i` 除以 `m` 的绝对最小余数, `i = 1, 2, 3, 4`:
    <span class="formula">
      `y_i -= x_i` `(mod m)`, `quad i = 1, 2, 3, 4`.
    </span>
    则 `y_i` 不全为零, 且绝对值小于 `m//2` (注意 `m` 是奇数).  因此
    <span class="formula">
      `0 lt sum_(i=1)^4 y_i^2 lt 4(m/2)^2 = m^2`,
    </span>
    且
    <span class="formula">
      `sum_(i=1)^4 y_i^2 -= sum_(i=1)^4 x_i^2 -= 0` `(mod m)`,
    </span>
    从而
    <span class="formula">
      `sum_(i=1)^4 y_i^2 = m q`,
      `quad 0 lt q lt m`.
    </span>
  </li>
  <li>下证 `p q` 可以表示成四个整数的平方和, 从而推翻假设.
    由四平方和恒等式, 令
    <span class="formula">
      `sum_(i=1)^4 z_i^2 = (sum_(i=1)^4 x_i^2) (sum_(i=1)^4 y_i^2)
      = m^2 p q`,
    </span>
    其中
    <span class="formula">
      `z_1 = x_1 y_1 + x_2 y_2 + x_3 y_3 + x_4 y_4`,<br/>
      `z_2 = x_1 y_2 - x_2 y_1 + x_3 y_4 - x_4 y_3`,<br/>
      `z_3 = x_1 y_3 - x_3 y_1 + x_4 y_2 - x_2 y_4`,<br/>
      `z_4 = x_1 y_4 - x_4 y_1 + x_2 y_3 - x_3 x_2`.
    </span>
    由 `x_i -= y_i (mod m)`, `i = 1, 2, 3, 4`, 有
    <span class="formula">
      `z_1 -= sum_(i=1)^4 x_i^2 -= 0` `(mod m)`,<br/>
      `z_i -= 0 (mod m)`, `i = 2, 3, 4`.
    </span>
    这指出 `m` 是 `z_1, z_2, z_3, z_4` 的公因数, 从而
    <span class="formula">
      `p q = sum_(i=1)^4 (z_i//m)^2`.
    </span>
    但 `q lt m`, 与 `m` 的最小性矛盾. 证毕.
  </li>
</ol>

<h2>Pell 方程</h2>

<p class="definition">
  设 `d` 为正整数, 且不是平方数, 下面的不定方程称为 <b>Pell 方程</b>:
  <span class="formula">
    `x^2 - d y^2 = 1`.
  </span>
</p>

<p class="theorem">
  <b>Pell 方程的幂形式解</b>
  将 Pell 方程的全部正整数解 `x_k, y_k` (后面会证明 Pell 方程确实有解)
  按 `lambda_k = x_k + sqrt d y_k` 的值由小到大排列, 有
  <span class="formula">
    `lambda_k = lambda_1^k`, `quad k = 1, 2, cdots`.
  </span>
  因此, 由 Pell 方程的<b>最小正整数解</b> `x_1, y_1` 可以轻松得到通解.
</p>

<ol class="proof">
  取共轭 `lambda_k' = x_k - sqrt d y_k`, 由 `x_k, y_k` 满足 Pell 方程知道
  `lambda_k lambda_k' = 1`. 下面证明, Pell 方程的正整数解 `x, y` 均满足
  `x + sqrt d y = lambda_1^k`, 其中 `k` 为某个正整数.
  <li>记 `x + sqrt d y = lambda_1^k`, 由于
    <span class="formula">
      `(x + sqrt d y)(x - sqrt d y)`
      `= lambda_1^k (lambda_1^k)'`
      `= lambda_1^k (lambda_1')^k`
      `= (lambda_1 lambda_1')^k = 1`,
    </span>
    所以 `x, y` 是一组正整数解.
  </li>
  <li>反之令 `x, y` 是一组正整数解, 且
    `lambda = x + sqrt d y` 不等于任何一个 `lambda_1^k`. 因为
    `lim_(k to oo) lambda_1^k = oo`, 可以设
    <span class="formula">
      `lambda_1^k lt lambda lt lambda_1^(k+1)`
    </span>
    同乘以 `lambda_1^-k = (lambda_1')^k` 得
    <span class="formula">
      `1 lt s + sqrt d t lt lambda_1`,
    </span>
    其中 `s + sqrt d t = lambda (lambda_1')^k`.
    注意到 `0 lt s - sqrt d t lt 1 lt s + sqrt d t`, 有
    <span class="formula">
      `s = 1/2((s + sqrt d t) + (s-sqrt d t)) gt 0`,<br>
      `t = 1/(2 sqrt d) ((s + sqrt d t) - (s - sqrt d t)) gt 0`,
    </span>
    且
    <span class="formula">
      `(s + sqrt d t)(s - sqrt d t)`
      `= lambda (lambda_1')^k lambda' lambda_1^k = 1`,
    </span>
    说明 `s, t` 也是一组正整数解, 然而 `s + sqrt d t lt lambda_1`,
    与 `lambda_1` 的最小性矛盾.
  </li>
</ol>

<p class="corollary">
  设 `d in ZZ^+` 不是平方数, 若不定方程 `x^2 - d y^2 = n` 有最小正整数解
  `x_0, y_0`, 则通解 `mu = x + sqrt d y` 由下式给出:
  <span class="formula">
    `mu_k = mu_0 lambda_1^k`, `quad k = 0, 1, 2, cdots`.
  </span>
  其中 `lambda_1` 对应 Pell 方程 `x^2 - d y^2 = 1` 的最小正整数解.
</p>

<ol class="proof">
  <li>首先验证 `mu_k = x_k + sqrt d y_k` 确实给出方程的解. 我们有
    <span class="formula">
      `(x_k + sqrt d y_k)(x_k - sqrt d y_k)`
      `= mu_k mu_k'`
      `= mu_0 mu_0' lambda_1^k (lambda_1')^k`
      `= mu_0 mu_0'`
      `= n`.
    </span>
  </li>
  <li>反之令 `x, y` 是一组正整数解, 且 `mu = x + sqrt d y`, 类似可证
    ??
  </li>
</ol>

<ol class="example">
  <li>稍加尝试可以知道,
  不定方程 `x^2 - 2 y^2 = 1` 的最小正整数解为 `(3, 2)`
  (依次尝试 `y = 1, 2, 3...`, 看 `1 + 2y^2` 何时为平方数).
  记 `lambda = 3 + 2 sqrt 2`, 则
  <span class="formula">
    `lambda^2 = 17+12√2`,
    `lambda^3 = 99+70√2`,
    `lambda^4 = 577+408√2`,
    `cdots`
  </span>
  对应于正整数解 `(17, 12)`, `(99, 70)`, `(577, 408)`, `cdots`.
  </li>
  <li>不定方程 `x^2 - 2 y^2 = 2` 的最小正整数解为 `(2, 1)`.
    这个方程的通解由下式生成:
    <span class="formula">
      `(2+√2)(3+2√2)^n`, `quad n = 0, 1, 2, cdots`
    </span>
    即
    <span class="formula">
      `2+√2`, `10+7√2`, `58+41√2`, `338+239√2`, `1970+1393√2`, `cdots`
    </span>
    其中 `(3, 2)` 是 1. 中方程的最小正整数解.
  </li>
</ol>

<p class="example">
  化简 `root 3 (20+14sqrt2)`.
</p>

<p class="solution">
  记 `lambda = x + y sqrt2`, 其共轭 `lambda' = x - y sqrt2`.
  如果 `lambda^3 = 20+14 sqrt2`, 则有
  <span class="formula">
    `(x^2 - 2 y^2)^3`
    `= (lambda lambda')^3`
    `= lambda^3 (lambda^3)'`
    `= (20 + 14 sqrt2)(20-14 sqrt2) = 2^3`.
  </span>
  解不定方程
  <span class="formula">
    `x^2 - 2 y^2 = 2`,
  </span>
  得到最小正整数解 `x = 2`, `y = 1`,
  发现恰有 `root 3 (20+14sqrt2) = 2 + sqrt 2`.
</p>

<p class="remark">
  若 `d` 是正整数且不是平方数, 不定方程 `x^2 - d y^2 = n^k`
  有正整数解 `x_k, y_k`,
  问 `x^2 - d y^2 = n` 是否有正整数解 `x_1, y_1`, 使得
  <span class="formula">
    `(x_1 + sqrt d y_1)^k = x_k + sqrt d y_k` ?
  </span>
</p>

<p>我们来说明 Pell 方程确实有解.</p>

<div class="theorem p">
  <b>Pell 方程的连分数解</b>
  设 `d in ZZ^+` 不是平方数, `p_k//q_k` 是 `sqrt d` 的简单连分数的第 `k`
  个收敛子. 记这个连分数的循环节长度为 `n`, 则
  <span class="formula">
    `p_(j n-1)^2 - d q_(j n-1)^2 = (-1)^(j n)`,
    `quad j = 1, 2, 3, cdots`.
  </span>
  上式给出了 Pell 方程 `x^2 - d y^2 = +-1` 的所有正整数解 `(p_(j n-1),
  q_(j n-1))`.  具体列表如下:
  <table>
    <tr>
      <td></td>
      <td>`x^2 - d y^2 = 1`</td>
      <td>`x^2 - d y^2 = -1`</td>
    </tr>
    <tr>
      <td>`n` 为偶数</td>
      <td>`j = 1, 2, 3, ...`</td>
      <td>无解</td>
    </tr>
    <tr>
      <td>`n` 为奇数</td>
      <td>`j = 2, 4, 6, ...`</td>
      <td>`j = 1, 3, 5, ...`</td>
    </tr>
  </table>
</div>

<h2>椭圆曲线</h2>

<p class="example">
  设直线 `y = k x + c` 与椭圆曲线 `y^2 = x^3 + a x + b`
  交于 `P_i(x_i, y_i)` `(i = 1, 2, 3)` 三点 (当其中两点重合时,
  直线与曲线相切). 联立方程, 由 Vieta 定理知
  <span class="formula">
    `x_1 + x_2 + x_3 = k^2`.
  </span>
  于是当已知 `P_1`, `P_2` 时, `P_3` 的坐标为
  <span class="formula">
        `x_3 = k^2 - x_1 - x_2`,<br/>
    `y_3 = y_1 + k(x_3-x_1)`
    `= y_2 + k(x_3-x_2)`.
  </span>
  称 `P_3` 关于 `x` 轴的对称点 `Q` 为 `P_1` 与 `P_2` 的和, 记为
  `Q = P_1 + P_2`.
  椭圆曲线上的全体有理点关于这一 "加法" 构成 Abel 群.
</p>

<p class="example">
  [来自 <a href="https://zhuanlan.zhihu.com/p/33853851">知乎专栏</a>]
  求这个不定方程的正整数解:
  <span class="formula">
    `(🍎️)/(🍌️+🍍️) + (🍌️)/(🍍️+🍎️) + (🍍️)/(🍎️+🍌️) = 4`,<br>
    `(a)/(b+c) + (b)/(c+a) + (c)/(a+b) = 4`.
  </span>
</p>

<p class="solution">
  此题可以通过椭圆代数曲线的理论解决.  一组可能的解是
  <span class="formula break-any">
    a=154476802108746166441951315019919837485664325669565431700026634898253202035277999,<br/>
    b=36875131794129999827197811565225474825492979968971970996283137471637224634055579,<br/>
    c=4373612677928697257861252602371390152816537558161613618621437993378423467772036.
  </span>
  首先该方程是齐次的: 若 `(a,b,c)` 是解, 则 `(t a, t b, t c)` 也是解.
  方程变形为
  <span class="formula">
    `a^3+b^3+c^3 = 3(a^2 b+a b^2+a^2 c+a c^2+b^2 c+b c^2) + 5abc`.
  </span>
  作代换 (??)
  <span class="formula">
    `a = (56-x+y)/(56-14x)`,
    `quad b = (56-x-y)/(56-14x)`,
    `quad c = (-28-6x)/(28-7x)`,
  </span>
  即
  <span class="formula">
    `x = -28(a+b+2c)/(6a+6b-c)`,
    `quad y = 364(a-b)/(6a+6b-c)`,
  </span>
  方程化为
  <span class="formula">
    `gamma: quad y^2 = x^3 + 109 x^2 + 224 x`.
  </span>
  代数曲线 `gamma` 上存在有理点 `P = (-100, 260)`.
  过 `P` 作 `gamma` 的切线, 与 `gamma` 交于另一点 `Q`, 点 `Q` 关于 `x`
  轴的对称点记为 `2P`:
  <span class="formula">
    2P = P + P = (8836/25, -950716/125)
  </span>
  连接 `P` 与 `2P` 两点, 所得直线与 `gamma` 交于另一点, 该点关于 `x`
  轴的对称点记为 `3P`:
  <span class="formula">
    3P = P + 2P = (-731025/11881, 527529870/1295029)
  </span>
  类似得到
  <span class="formula break-any">
    6P = 3P + 3P = (252785840525963937198721/13225347684085115955600, -343764653760831645784970282294394569/1520934975898868459000385442296000),
  </span>
  <span class="formula break-any">
  9P = 3P + 6P = (-66202368404229585264842409883878874707453676645038225/13514400292716288512070907945002943352692578000406921, 58800835157308083307376751727347181330085672850296730351871748713307988700611210/1571068668597978434556364707291896268838086945430031322196754390420280407346469).
  </span>
  将 `9P` 这一点代回原变元 a, b, c:
  <span class="formula break-any">
    (a,b,c) = (652194680638776317370751188686261401138670498641722947/826345176768069653846031682295795260307016241032351542, 72627067629030455550043880234643101653454184810448427/385489402115598358968822193146517732601759618776822382, 18811002229321433251069036843190834369329875858835562/841819787025663175191882291647234536827567920526661363).
  </span>
  放大适当倍数即得答案.
</p>

<script src="../../js/note.js?type=math"></script>
</body>
</html>
